#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2021/5/13 00:43
# @Author  : Samge
from utils import test_data
from utils.coast_time import coast_time


@coast_time
def insertion_sort(arr, desc):
    """
    插入排序
        取列表中右边【未排序】的数据 跟 左边【已排序】的数据一一对比，如果当前值比左值还小，则继续往左移动
    :param arr: 要处理的列表
    :param desc: True-降序，False-升序
    :return: list 排序好的列表
    """
    if not arr:
        raise ValueError('参与排序的列表不能为空')
    max_size = len(arr)
    for i_un in range(max_size):
        curr_num = arr[i_un]
        pre_index = i_un - 1
        while pre_index >= 0 and curr_num < arr[pre_index]:
            arr[pre_index+1], arr[pre_index] = arr[pre_index], arr[pre_index+1]
            pre_index -= 1
    if desc:
        arr.reverse()
    return arr


if __name__ == '__main__':
    test_lst = test_data.get_test_arr(10, shuffle=True, reverse=False)
    print(insertion_sort(test_lst, desc=True))
    print(insertion_sort(test_lst, desc=False))
